/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
    	if(pHead == nullptr)
    		return nullptr;
    	int size = loopSize(pHead);
    	ListNode *pa = pHead, *pb = pHead;
    	if(size == 0)
    		return nullptr;
    	while(size > 0)
    	{
    		pb = pb->next;
			--size;
    	}
    	while(pa != pb)
    	{
    		pa = pa->next;
    		pb = pb->next;
    	}
    	return pa;
    }

    int loopSize(ListNode *pHead)
    {
    	ListNode *inside = findInside(pHead);
    	if(inside == nullptr)
    		return 0;
    	ListNode *p = inside->next;
    	int cnt = 1;
    	while(p!=inside)
    	{
    		p = p->next;
    		++cnt;
    	}
    	return cnt;
    }

    ListNode *findInside(ListNode *pHead)
    {
    	ListNode* pa= pHead,*pb = pHead;
    	pa = pa->next;
    	if(!pa)
    		return nullptr;
    	pb = pb->next->next;
    	while(pa != pb)
    	{
    		pa = pa->next;
    		if(!pa)
    			return nullptr;
    		pb = pb->next->next;
    	}
    	return pa;
    }
};
